1. Field Of The Invention
The invention relates to systems and methods for in-memory database access, and more particularly to systems and methods for insertion, deletion and access in a database organized as a skip list using compressed search keys.
2. Background Information
Telecommunications networks use databases to store very large amounts of information. One such application is the translation of 800 telephone numbers to geographic termination numbers. Another application is validation of credit card calls. In both applications, there are millions of records which must be searched. The search must be performed while a customer is waiting for a call to be completed, so it must be completed within a few seconds. Large numbers of search requests may arrive simultaneously, but again, each search cannot take more than a few seconds. Current art disk-based database systems do not have the throughput to meet these requirements. Therefore, current art systems are generally memory based.
Since a database may contain millions of records, a memory-based database system must contain a large amount of memory. Systems having one gigabyte of main memory are not unusual. Nevertheless, increased calling, internationalization of credit cards and increasing users of 800 numbers have increased the size of such databases to the point that even one gigabyte may not be sufficient. Systems with more memory are possible, but their cost is very high.
A better solution to the problem is to compress the database. Compression of the data fields is well known in the art, but additional memory usage improvement can be had by compressing the key values as well. One way to compress key values is to store the nodes in sorted order by key value with the search key for each node based on the difference between the key value for that node and the key value for the previous node. The problem is to create an in memory data structure that allows both key compression and quick indexed retrieval.
3. Other Publications
W. Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, 33(6)668-676(1990).
W. Pugh, A Skip List Cookbook, University of Maryland (1990).